import java.lang.annotation.Target;

/**
 * @author: 最帅的的乐乐
 * @date: 2025-02-17 10:03 星期一
 * @motto the harder, the luckier。
 */

public class _34_SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if(len == 0) {
            return new int[]{-1, -1};
        }
        int firstPosition = findFirstPosition(nums, target);
            if(firstPosition == -1) {
                return new int[]{-1, -1};
            }

        int lastPosition = findLastPosition(nums, target);
            return new int []{firstPosition, lastPosition};
        }


    private static int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        while(left < right){
            // 加1 是 偏向右边查找
            int mid = (left + right+1) >>>1;
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] == target) {

                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }


    public int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = (left + right) >>>1;
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] == target) {
                right = mid;
            }else{
                right = mid - 1;
            }
        }
        if(nums[left] == target) {
            return left;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        int target = 8;

        int lastIndex = findLastPosition(nums, target);

        if (lastIndex != -1) {
            System.out.println("The last occurrence of " + target + " is at index: " + lastIndex);
        } else {
            System.out.println("The target value " + target + " is not found.");
        }
    }

}
